package SubjectTree.Two;

import java.util.Deque;
import java.util.LinkedList;

import Utility.TreeNode;

public class IsBalanced {

/**
 * 难度：简单
 * 
 * 110. 平衡二叉树
 * 	给定一个二叉树，判断它是否是高度平衡的二叉树。
 * 	本题中，一棵高度平衡二叉树定义为：
 * 	一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
 * 	
 * 示例 1：
 * 	输入：root = [3,9,20,null,null,15,7]
 * 	输出：true
 * 	
 * 示例 2：
 * 	输入：root = [1,2,2,3,3,null,null,4,4]
 * 	输出：false
 * 	
 * 示例 3：
 * 	输入：root = []
 * 	输出：true
 * 	
 * 提示：
 * 	树中的节点数在范围 [0, 5000] 内
 * 	-104 <= Node.val <= 104
 *
 * */
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		IsBalanced ib = new IsBalanced();
		System.out.println(ib.isBalanced2(TreeNode.MkTree("[3,9,20,null,null,15,7]")));
	}
	//自己写（前序扫描）
	public boolean isBalanced(TreeNode root) {
		Deque<TreeNode> deque = new LinkedList<>();
		TreeNode node = root;
		while(!deque.isEmpty()||node!=null) {
			while(node!=null) {
				//分别把左子树和右子树放入层级计算深度
				if(Math.abs(getDepth(node.left) - getDepth(node.right))>1) {
					return false;
				} 
				deque.push(node);
				node = node.left;
			}
			node = deque.pop();
			node = node.right;
		}
		return true;
    }
	//用层级扫描树的深度
	public int getDepth(TreeNode root) {
		if(root==null)return 0;
		Deque<TreeNode> deque = new LinkedList<>();
		deque.offer(root);
		int depth=0;
		while(!deque.isEmpty()) {
			int currentLevelSize = deque.size();
			for(int i=0;i<currentLevelSize;i++) {
				TreeNode node = deque.poll();
				if(node.left!=null) deque.offer(node.left);
				if(node.right!=null) deque.offer(node.right);
			}
			depth++;
		}
		return depth;
    }
	
	//自己写（递归,使用后续遍历）
	public boolean isBalanced_1(TreeNode root) {
		return traversal(root) == -1?false:true;
    }
	public int traversal(TreeNode root) {
		if(root==null)return 0;
		int leftCount = traversal(root.left);
		if(leftCount==-1)return -1;
		int rightCount = traversal(root.right);
		if(rightCount==-1)return -1;
		
		int Count = 0;
		if(Math.abs(leftCount - rightCount)>1) {
			Count = -1;
		}else{
			Count = 1+Math.max(leftCount,rightCount);
		}
		return Count;
	}
	
	//方法一：自顶向下的递归
	public boolean isBalanced1(TreeNode root) {
        if (root == null) {
            return true;
        } else {
            return Math.abs(height1(root.left) - height1(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
        }
    }
    public int height1(TreeNode root) {
        if (root == null) {
            return 0;
        } else {
            return Math.max(height1(root.left), height1(root.right)) + 1;
        }
    }
    
    //方法二：自底向上的递归
    public boolean isBalanced2(TreeNode root) {
        return height2(root) >= 0;
    }
    public int height2(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftHeight = height2(root.left);
        int rightHeight = height2(root.right);
        if (leftHeight == -1 || rightHeight == -1 || Math.abs(leftHeight - rightHeight) > 1) {
            return -1;
        } else {
            return Math.max(leftHeight, rightHeight) + 1;
        }
    }
}
